package com.mid;

import java.util.Stack;

/**
 * Created by Lxk on 2020/2/29.
 */
public class Solution306 {

    private Stack<String> numStack = new Stack<>();

    private boolean res = false;

    private String addNum(String num, String num2) {
        int pos = num.length() - 1, pos2 = num2.length() - 1;
        StringBuffer res = new StringBuffer();
        boolean isAdd = false;
        while (pos >= 0 && pos2 >= 0) {
            int curPosSum = (num.charAt(pos) - '0') + (num2.charAt(pos2) - '0') + (isAdd ? 1 : 0);
            int curNum = curPosSum % 10;
            res.append(curNum);
            isAdd = curPosSum >= 10;
            pos--;
            pos2--;
        }
        if (pos2 >= 0) {
            while (pos2 >= 0) {
                int curPosSum = (num2.charAt(pos2) - '0') + (isAdd ? 1 : 0);
                int curNum = curPosSum % 10;
                res.append(curNum);
                isAdd = curPosSum >= 10;
                pos2--;
            }
        }
        if (pos >= 0) {
            while (pos >= 0) {
                int curPosSum = (num.charAt(pos) - '0') + (isAdd ? 1 : 0);
                int curNum = curPosSum % 10;
                res.append(curNum);
                isAdd = curPosSum >= 10;
                pos--;
            }
        }
        if (isAdd) {
            res.append(1);
        }
        return res.reverse().toString();
    }

    private void judgeAdditiveNumber(String num, int beginPos) {
        if (beginPos >= num.length()) {
            if (numStack.size() >= 3) {
                String pre = numStack.get(1), prePre = numStack.get(0);
                for (int i = 2; i < numStack.size(); i++) {
                    if (!addNum(pre, prePre).equals(numStack.get(i))) {
                        return;
                    } else {
                        prePre = pre;
                        pre = numStack.get(i);
                    }
                }
                for (String val : numStack) {
                    System.out.println(val);
                }
                res = true;
            }
            return;
        }
        if (res) {
            return;
        }
        for (int i = 1; i <= num.length() - beginPos; i++) {
            if (num.charAt(beginPos) == '0' && i > 1) {
                return;
            }
            String val = num.substring(beginPos, beginPos + i);
            if (!res) {
                if (numStack.size() >= 2 && (val.equals(addNum(numStack.peek(), numStack.get(numStack.size() - 2))))) {
                    numStack.push(val);
                    judgeAdditiveNumber(num, beginPos + i);
                    numStack.pop();
                } else if (numStack.size() < 2) {
                    numStack.push(val);
                    judgeAdditiveNumber(num, beginPos + i);
                    numStack.pop();
                }
            }
        }
    }

    public boolean isAdditiveNumber(String num) {
        if (num.length() <= 2) {
            return false;
        }
        for (int i = 1; i <= num.length() / 2; i++) {
            judgeAdditiveNumber(num, 0);
        }
        return res;
    }

    public static void main(String[] args) {
//        System.out.println(Integer.MAX_VALUE);
//        Integer val = Integer.valueOf("12012122436");
        String num = "11111111111011111111111";
        Solution306 solution306 = new Solution306();
        System.out.println(solution306.isAdditiveNumber(num));
    }

}
